package com.itheima.leetcode.od.b.backtracking;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.stream.Collectors;

/**
 * <h3>套皮Leetcode698-划分为k个相等的子集</h3>
 * (A卷,100分)- 星际篮球争霸赛（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 在星球争霸篮球赛对抗赛中，最大的宇宙战队希望每个人都能拿到MVP，MVP的条件是单场最高分得分获得者。
 * 可以并列所以宇宙战队决定在比赛中尽可能让更多队员上场，并且让所有得分的选手得分都相同，
 * 然而比赛过程中的每1分钟的得分都只能由某一个人包揽。
 * <p>
 * 输入描述
 * <p>
 * 输入第一行为一个数字 t ，表示为有得分的分钟数 1 ≤ t ≤ 50
 * 第二行为 t 个数字，代表每一分钟的得分 p， 1 ≤ p ≤ 50
 * <p>
 * 输出描述
 * <p>
 * 输出有得分的队员都是MVP时，最少得MVP得分。
 * <p>
 * 用例
 * <p>
 * 输入	9
 * 5 2 1 5 2 1 5 2 1
 * 输出	6
 * 说明	样例解释 一共 4 人得分，分别都是 6 分
 * 5 + 1 ， 5 + 1 ， 5 + 1 ， 2 + 2 + 2
 */
public class InterstellarBasketballChampionship {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();

        LinkedList<Integer> link = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            link.add(sc.nextInt());
        }*/

        int m = 9;
        LinkedList<Integer> link = Arrays.stream("5 2 1 5 2 1 5 2 1".split(" "))
                .mapToInt(Integer::parseInt)
                .boxed()
                .collect(Collectors.toCollection(LinkedList::new));

        System.out.println(getResult(link, m));
    }

    public static int getResult(LinkedList<Integer> link, int m) {
        link.sort((a, b) -> b - a); // 大顶堆

        int sum = link.stream()
                .mapToInt(Integer::intValue)
                .sum();

        while (m >= 1) {
            // 根据网友指正，由于canPartition方法中会删除link元素，因此我们不能直接传递link过去，需要传递link备份，否则会影响下一次count判断
            //      if (canPartitionMSubsets(link, sum, m)) return sum / m;
            LinkedList<Integer> link_cp = new LinkedList<>(link);
            if (canPartitionMSubsets(link_cp, sum, m)) {
                return sum / m;
            }
            m--;
        }

        return sum;
    }

    /**
     * 类似球视角的回溯
     *
     * @param link
     * @param sum
     * @param m
     * @return
     */
    public static boolean canPartitionMSubsets(LinkedList<Integer> link, int sum, int m) {
        if (sum % m != 0) {
            return false;
        }

        int subSum = sum / m;

        if (subSum < link.get(0)) {
            return false;
        }

        //    while (link.get(0) == subSum) { // 此段代码可能会出现越界
        while (link.size() > 0 && link.get(0) == subSum) {
            link.removeFirst();
            m--;
        }

        int[] buckets = new int[m];
        return partition(link, 0, buckets, subSum);
    }

    public static boolean partition(LinkedList<Integer> link, int index, int[] buckets, int subSum) {
        if (index == link.size()) {
            return true;
        }

        int select = link.get(index);

        for (int i = 0; i < buckets.length; i++) {
            if (i > 0 && buckets[i] == buckets[i - 1]) {
                continue;
            }
            if (select + buckets[i] <= subSum) {
                buckets[i] += select;
                // 递归装下一个球
                if (partition(link, index + 1, buckets, subSum)) {
                    return true;
                }
                // 如果这种策略无法装完所有球，则回溯
                buckets[i] -= select;
            }
        }

        return false;
    }
}